package club.xiaojiawei.binarytree;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 5/9/22 11:09 PM
 * @question 199. 二叉树的右视图
 * @description 给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
 */
public class RightSideView199 {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
//        TreeNode left = new TreeNode(2);
//        TreeNode right = new TreeNode(3);
//        TreeNode node = new TreeNode(6);
//        node.left = new TreeNode(7);
//        right.left = node;
//        left.right = new TreeNode(5);
//        right.right = new TreeNode(4);
//        root.left = left;
//        root.right = right;
        List<Integer> result = rightSideView(root);
        System.out.println(result);
    }

    /**
     *  递归
     * @param root
     * @return
     */
    public static List<Integer> rightSideView(TreeNode root) {
        if (root == null){
            return new ArrayList<>();
        }
        Integer[] result = new Integer[height(root)];
        recursion(result, root, 0);
        return Arrays.asList(result);
    }

    /**
     * 求出树的高度
     * @param root
     * @return
     */
    public static int height(TreeNode root){
        return Math.max(root.right == null? 0 : height(root.right), root.left == null? 0 : height(root.left)) + 1;
    }


    public static void recursion(Integer[] arr, TreeNode node, int index){
        if (node == null){
            return;
        }
        if (arr[index] == null){
            arr[index] = node.val;
        }
        recursion(arr, node.right, index + 1);
        recursion(arr, node.left, index + 1);
    }

    static ArrayList<Integer> dfsLists = new ArrayList<>();

    /**
     * 民间-递归
     * @param root
     * @return
     */
    public static List<Integer> rightSideView2(TreeNode root) {
        if(root == null){
            return dfsLists;
        }
        dfs(root,0);
        return dfsLists;
    }
    public static void dfs(TreeNode node,int depth){
        if (node == null){
            return;
        }
        if (depth == dfsLists.size()){
            dfsLists.add(node.val);
        }
        dfs(node.right,++depth);
        dfs(node.left,depth);
    }

    static class TreeNode{

        private int val;

        private TreeNode left;

        private TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }

        public int getVal() {
            return val;
        }

        public void setVal(int val) {
            this.val = val;
        }

        public TreeNode getLeft() {
            return left;
        }

        public void setLeft(TreeNode left) {
            this.left = left;
        }

        public TreeNode getRight() {
            return right;
        }

        public void setRight(TreeNode right) {
            this.right = right;
        }
    }
}
